﻿using System;
using System.Collections.Generic;

namespace IOP.Algorithm.Search
{
    /// <summary>
    /// Boyer-Moore字符串搜索算法
    /// </summary>
    public static class BM
    {
        /// <summary>
        /// BM算法
        /// </summary>
        /// <param name="text">匹配字符</param>
        /// <param name="pattern">模式串</param>
        /// <param name="bmBc">坏字符字典</param>
        /// <param name="bmGs">好后缀数组</param>
        /// <returns></returns>
        public static int BoyerMoore(this string text, string pattern, Dictionary<char, int> bmBc, int[] bmGs)
        {
            int m = pattern.Length;
            int n = text.Length;
            int j = 0;
            int i = 0;
            int count = 0;
            while (j <= n - m)
            {
                for (i = m - 1; i >= 0 && pattern[i] == text[i + j]; i--) count++;
                if (i < 0) return j;
                else j += Math.Max(GetBmBc(text[i + j], bmBc, m) - m + 1 + i, bmGs[i]);
            }
            return -1;
        }

        /// <summary>
        /// BM算法
        /// </summary>
        /// <param name="text">匹配字符</param>
        /// <param name="pattern">模式串</param>
        /// <returns></returns>
        public static int BoyerMoore(this string text, string pattern)
        {
            int m = pattern.Length;
            int n = text.Length;
            int j = 0;
            int i = 0;
            int count = 0;

            PreBmBc(pattern, out Dictionary<char, int> bmBc);
            PreBmGs(pattern, out int[] bmGs);

            while (j <= n - m)
            {
                for (i = m - 1; i >= 0 && pattern[i] == text[i + j]; i--) count++;
                if (i < 0) return j;
                else j += Math.Max(GetBmBc(text[i + j], bmBc, m) - m + 1 + i, bmGs[i]);
            }
            return -1;
        }

        /// <summary>
        /// 计算坏字符并输出字典
        /// </summary>
        /// <param name="pattern"></param>
        /// <param name="patLength"></param>
        /// <param name="bmBc"></param>
        public static void PreBmBc(string pattern, out Dictionary<char, int> bmBc)
        {
            int patLength = pattern.Length;
            bmBc = new Dictionary<char, int>();
            for (int i = patLength - 2; i >= 0; i--)
            {
                if (!bmBc.ContainsKey(pattern[i]))
                {
                    bmBc.Add(pattern[i], patLength - i - 1);
                }
            }
        }

        /// <summary>
        /// 计算好后缀并输出数组
        /// </summary>
        /// <param name="pattern"></param>
        /// <param name="patLength"></param>
        /// <param name="bmGs"></param>
        public static void PreBmGs(string pattern, out int[] bmGs)
        {
            int patLength = pattern.Length;
            int i, j;
            bmGs = new int[patLength];
            Suffix(pattern, patLength, out int[] suffix);
            for (i = 0; i < patLength; i++)
                bmGs[i] = patLength;
            j = 0;
            for (i = patLength - 1; i >= 0; i--)
            {
                if (suffix[i] == i + 1)
                {
                    for (; j < patLength - 1 - i; j++)
                    {
                        if (bmGs[j] == patLength)
                            bmGs[j] = patLength - 1 - i;
                    }
                }
            }
            for (i = 0; i <= patLength - 2; i++)
            {
                bmGs[patLength - 1 - suffix[i]] = patLength - 1 - i;
            }
        }

        /// <summary>
        /// 计算suffix数组
        /// </summary>
        /// <param name="pattern"></param>
        /// <param name="patLength"></param>
        /// <param name="suffix"></param>
        private static void Suffix(string pattern, int patLength, out int[] suffix)
        {
            int f = 0, g = 0, i;
            suffix = new int[patLength];
            suffix[patLength - 1] = patLength;
            g = patLength - 1;
            for (i = patLength - 2; i >= 0; --i)
            {
                if (i > g && suffix[i + patLength - 1 - f] < i - g)
                    suffix[i] = suffix[i + patLength - 1 - f];
                else
                {
                    if (i < g)
                        g = i;
                    f = i;
                }
                while (g >= 0 && pattern[g] == pattern[g + patLength - 1 - f]) { --g; }
                suffix[i] = f - g;
            }
        }

        /// <summary>
        /// 获取BmBc字典的数据
        /// </summary>
        /// <param name="c"></param>
        /// <param name="bmBc"></param>
        /// <param name="m"></param>
        /// <returns></returns>
        private static int GetBmBc(char c, Dictionary<char, int> bmBc, int m)
        {
            if (bmBc.ContainsKey(c)) return bmBc[c];
            else return m;
        }
    }
}
